package LeetCode.interview;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
	 Given a collection of intervals, merge all overlapping intervals.
	
	For example,
	Given [1,3],[2,6],[8,10],[15,18],
	return [1,6],[8,10],[15,18].
题目大意

	
解题思路
		题意：有很多个区间，把有重叠的区间合并。
	
	思路：先排序，然后检查相邻两个区间，看前一个区间的结尾是否大于后一个区间的开始，注意前一个区间包含后一个区间的情况。
	
	用Java自带的sort()方法，只要自己重写compare()方法即可。
 * @Date 2017-10-02 22：55
 */
public class _056_Merge_Intervals {
	 public class Interval {
		 Integer start;
		 Integer end;
		 Interval() { start = 0; end = 0; }
		 Interval(int s, int e) { start = s; end = e; }
	 }
	/*
	 * 排序
	 */
	 private Comparator<Interval> comparator = new Comparator<_056_Merge_Intervals.Interval>() {
		@Override
		public int compare(Interval o1, Interval o2) {
			return o1.start.compareTo(o2.start);
		}
	};
	 public List<Interval> merge(List<Interval> intervals) {
		 List<Interval> rs = new ArrayList<>();
		 if (intervals==null || intervals.size()==0)	return rs;
		 //先排序
		 Collections.sort(intervals, comparator);
		 int preStart = intervals.get(0).start, preEnd = intervals.get(0).end; 
		 for (int i = 0; i < intervals.size(); i ++) {
			 Interval curInterval = intervals.get(i);
			 if (curInterval.start > preEnd) {
				 //将之前区间加入
				 rs.add(new Interval(preStart, preEnd));
				 preStart = curInterval.start;
				 preEnd = curInterval.end;
			 } else {
				 preEnd = Math.max(preEnd, curInterval.end);
			 }
		 }
		 rs.add(new Interval(preStart, preEnd));
		 return rs;
	 }
	 public void traverse(int[] nums) {
	 	for (int i : nums) {
			LogUtils.print(i);
		}
	 }
    
	 public static void main(String[] args) {
		_056_Merge_Intervals obj = new _056_Merge_Intervals();

		obj.merge(new LinkedList<_056_Merge_Intervals.Interval>());
	 }

}
